package 算法.leetcode.labuladong.数组和链表;

/**
 * https://leetcode.cn/problems/range-sum-query-2d-immutable/
 *
 * @author lchenglong
 * @date 2022/6/15
 */
public class 二维区域和检索_矩阵不可变 {
    static class NumMatrix {
        int[][] preSums ;

        public NumMatrix(int[][] matrix) {
            int m = matrix.length,n=matrix[0].length;
            preSums = new int[m+1][n+1];
            for (int i=1;i<=m;i++) {
                for (int j=1;j<=n;j++){
                    preSums[i][j] = preSums[i][j-1]+preSums[i-1][j]-preSums[i-1][j-1]+matrix[i-1][j-1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            //      row1
            //  col1
            //           row2
            //       col2
            return preSums[row2+1][col2+1]-preSums[row1][col2+1]-preSums[row2+1][col1]+preSums[row1][col1];
        }
    }

}
